#include <cstdio>
#include <cstring>
#include <queue>
#define pair std::pair<int, int>

const int N = 100005;
int t, n, m, k, p, cnt;
int e_cnt, heads[N], sdis[N], tdis[N], u[N << 1], v[N << 1], w[N << 1], in[N], topn[N],
    f[N][55];
std::priority_queue<pair, std::vector<pair>, std::greater<pair> > pq;
std::queue<int> q;

struct Edge {
  int v, nxt, w;
} e[N << 1];

inline void add(int u, int v, int w) {
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt, e[e_cnt].w = w;
}

inline void dij(int s, int *dis) {
  dis[s] = 0, pq.push(std::make_pair(0, s));
  while (!pq.empty()) {
    int d = pq.top().first, u = pq.top().second;
    pq.pop();
    if (d != dis[u]) continue;
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (dis[v = e[i].v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        pq.push(std::make_pair(dis[v], v));
      }
    }
  }
}

inline void topu() {
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), topn[++cnt] = u;
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (!--in[v = e[i].v]) q.push(v);
    }
  }
}

inline void solve() {
  e_cnt = 0, cnt = 0;
  memset(in, 0, sizeof(in));
  memset(heads, 0, sizeof(heads));
  memset(sdis, 0x3f, sizeof(sdis));
  memset(tdis, 0x3f, sizeof(tdis));

  scanf("%d%d%d%d", &n, &m, &k, &p);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &u[i], &v[i], &w[i]);
    add(u[i], v[i], w[i]);
  }
  dij(1, sdis);
  e_cnt = 0;
  memset(heads, 0, sizeof(heads));
  for (int i = 1; i <= m; ++i) add(v[i], u[i], w[i]);
  dij(n, tdis);
  e_cnt = 0;
  memset(heads, 0, sizeof(heads));
  for (int i = 1; i <= m; ++i) {
    if (sdis[u[i]] + tdis[v[i]] + w[i] <= sdis[n] + k &&
        sdis[u[i]] + w[i] == sdis[v[i]]) {
      add(u[i], v[i], 0);
      in[v[i]]++;
    }
  }
  for (int i = 1; i <= m; ++i) {
    w[i] -= sdis[v[i]] - sdis[u[i]];
  }
  topu();
  for (int i = 1; i <= n; ++i)
    if (in[i]) return puts("-1"), void();
  memset(f, 0, sizeof(f));
  f[1][0] = 1;
  for (int i = 0; i <= k; ++i) {
    for (int j = 1, u; j <= cnt; ++j) {
      u = topn[j];
      for (int h = heads[u], v; h; h = e[h].nxt) {
        (f[v = e[h].v][i] += f[u][i]) %= p;
      }
    }
    for (int j = 1; j <= m; ++j)
      if (i + w[j] <= k && w[j]) (f[v[j]][i + w[j]] += f[u[j]][i]) %= p;
  }
  int ans = 0;
  for (int i = 0; i <= k; ++i) (ans += f[n][i]) %= p;
  printf("%d\n", ans);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("P3953 逛公园.in", "r", stdin);
  freopen("P3953 逛公园.out", "w", stdout);
#endif
#endif

  scanf("%d", &t);
  while (t--) solve();
  return 0;
}